package 动态规划;

/**
 *
 * @author hunbird
 *
 *
 */
public class 动态规划算法_最大子矩阵 {
	public static int maxSum(int n, int[] a) {
		int sum = a[0], pre = a[0];
		for (int i = 1; i < n; i++) {
			pre = Math.max(pre + a[i], a[i]);
			sum = Math.max(pre, sum);
		}
		System.out.println("=" + sum);
		return sum;
	}

	public static int maxMatrix(int[][] a) {
		int ar = a.length;
		int ac = a[0].length;
		int[] b = new int[ac + 1];
		int sum = 0;
		for (int i = 0; i < ar; i++) {
			b = new int[ac + 1];
			for (int k = i; k < ar; k++) {
				for (int m = 0; m < ac; m++) {
					b[m] += a[k][m];
				}
				int max = maxSum(b.length - 1, b);
				if (max > sum) {
					sum = max;
				}

			}
		}

		return sum;

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] a = { { 1, 2, -4 }, { 1, 2, -5 } };
		System.out.println("最大子矩阵和为：" + maxMatrix(a));

	}

}
